<head>
  <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<title>План лекций</title>
  <link href=styles/styles.css rel="stylesheet" type="text/css">
</head>
<h2>День 2. Динамика.Advanced</h2>
<ol>
  <li>Разбиения на слагаемые (10 минут)</li>
  <ol>
    <li>За O(n<sup>3</sup>) [sum, максимальное слагаемое], переход = перебираем, какое следующее</li>
    <li>За O(n<sup>2</sup>) [sum, максимальное слагаемое], два перехода</li>
    <li>Делаем память линейной.</li>
    <li>Две разные задачи: можно брать одинаковые слагаемые, все слагаемые должны быть различны</li>
    <li>Еще две задачи: максимальное слагаемое ровно k, максимальное слагаемое не более k за O(nk).</li>
    <li>Ровно на k слагаемых за O(nk) времени и O(n) памяти = перевернуть матрицу</li>
    <li>Ровно на k различных слагаемых за O(n sqrt n) и O(n) памяти: n -= k(k+1)/2</li>
  </ol></li>
  <li>Динамика по подмножествам</li>
  <ol>
    <li>Битовые операции: объединение, пересечение, разность, i-й элемент, является ли A подмножеством B</li>
    <li>Битовые операции: Количество бит в числе за O(1), старший бит за O(1)</li>
    <li>Гамильтонов путь за O(n<sup>2</sup>*2<sup>n</sup>)</li>
    <li>Гамильтонов цикл за O(n<sup>2</sup>*2<sup>n</sup>)</li>
    <li>Количество подклик в графе за O(2<sup>n</sup>*n<sup>2</sup>) и за O(2<sup>n</sup>*n) (битовые операции)</li>
    <li>Количество подклик в графе за O(2<sup>n</sup>) (два решения = рекурсивный перебор или динамика)</li>
    <li>Перебор всех подмножеств циклом for (b = A; b > 0; b--, b &= A)</li>
    <li>Перебор всех надмножеств циклом for (b = A; b < 2<sup>n</sup>; b++, b |= A)</li>
    <li>Количество способов разбить графа на подклики за O(3<sup>n</sup>)</li>
    <li>Рюкзак и meet-in-the-middle. O(2<sup>n/2</sup>).</li>
    <li>Количество подклик и meet-in-the-middle. O(2<sup>n/2</sup>).</li>
  </ol></li>
  <li>Динамика по дереву</li>
  <ol>
    <li>Нужно посчитать размер каждого из поддеревьев за O(n)</li>
    <li>Нужно найти для каждого поддерева максимальный по длине путь в поддереве за O(n)</li>
    <li>Для каждого ребра количество путей, которые по нему проходят.</li>
    <li>Нужно разрезать минимальное число ребер, чтобы одна из компонент связности имела размер ровно k. За O(n<sup>3</sup>)</li>
    <li>То же самое за O(n<sup>2</sup>)</li>
    <li>Количество корневых деревьев из n вершин (все вершины помечены) глубины не более d (ровно d) за O(n<sup>4</sup>)</li>
    <li>То же самое за O(n<sup>3</sup>) и O(n<sup>2</sup>logn)</li>
  </ol></li>
  <li>Задачи про подпоследовательности. Внесение функции в параметры. Измельчение перехода.</li>
  <ol>
    <li>Наибольшая общая с восстановлением ответа и битовым сжатием + метод четырех русских.</li>
    <li><span style="color: blue;"><i>Not read </i></span>Наибольшая возрастающая подпоследовательность за O(nlogn) [внесли функцию]</li>
    <li><span style="color: blue;"><i>Not read </i></span>Наибольшая общая возрастающая за O(n<sup>2</sup>) [измельчили переход]</li>
    <li><span style="color: blue;"><i>Not read </i></span>Количество различных подпоследовательностей за O(n)</li>
    <li><span style="color: blue;"><i>Not read </i></span>Кратчайшая последовательность, которая не является подпоследовательностью ни первой, ни второй. Алфавит = k. Решение за O(n<sup>2</sup>*k)</li>
    <li><span style="color: blue;"><i>Not read </i></span>Та же задача за O(n<sup>2</sup>)</li>
  </ol></li>
  <li>Динамика по профилю</li>
  <ol>
    <li>Количество замощений грида n x m доминошками за время m * 4<sup>n</sup></li>
    <li>Количество замощений грида n x m доминошками за время (log m) * 8<sup>n</sup> (m <= 10<sup>9</sup>)</li>
    <li>Количество замощений грида n x m доминошками за время mn * 2<sup>n</sup></li>
    <li>Способ писать динамику по скошенному профилю через рекурсию (перебор + отсечение запоминанием).</li>
    <li>Задача: сколько у грида n x m гамильтоновых циклов (ходить можно по 4-м направлениям). Решение динамикой по скошенному профилю.</li>
    <li>В предыдущей задаче можно закодировать профиль скобочной последовательностью.</li>
  </ol></li>
  <li>Лексмин ответ.</li>
  <ol>
    <li>Найти лексмин заполнение рюкзака размера w за O(nw)</li>
    <li>Найти лексмин общую подпоследовательность за O(n<sup>2</sup>*E) и за O(n<sup>2</sup>)?</li>
    <li>Общая задача: дан ориентированный ацикличный граф из n вершин и m ребер. На каждом ребре написан символ.</li>
    <ol>
      <li>Все символы на ребрах исходящих из вершины различны. Найти lexmin путь. O(m) [два решения: жадность и динамика]</li>
      <li>Найти lexmin кратчайший путь или максимальный путь. O(m). [а это как раз подпоследовательности...]</li>
      <li>Найти lexmin путь. Жадность работает O(mn) -- плохо. Идем с конца строим дерево с предподсчитанными хэшами на пути: O(mlogn).</li>
    </ol></li>
  </ol></li>
  <li>Сложные задачи (если останется время)</li>
  <ol>
    <li>Нужно найти в графе контролирующее множество. Ответ равен k. Решение этой задачи за O(2<sup>n/3</sup>) [урезанный алгоритм Робсона]</li>
    <li><span style="color: blue;"><i>Not read </i></span>Даны n точек на прямой. Нужно выбрать k из них так, чтобы сумма расстояний до выбранных точек была минимальна за O(n<sup>2</sup>) [фишка из Кнута]</li>
    <li><span style="color: blue;"><i>Not read </i></span>Есть n хороших строк длины не более n. За ход можно из текущей строки удалять любую из хороших строк (если она содержится, как подстрока). Нужно, чтобы в конце игры осташаяся строка была минимальной длины. O(n<sup>5</sup>).</li>
  </ol></li>
</ol>
